//
// Created by Admin on 2021/9/24.
//

#include "myGraph.h"
#include "queue/my_queue.h"
#include "stack/my_stack.h"

int getNodePos(pGraph graph,const char* name){
    for(int i=0;i<graph->node_size;i++){
        if(strcmp(graph->graphNodes[i].name,name)==0){
            return i;
        }
    }
    return -1;
}

pGraph initGraph(){
    pGraph graph = calloc(1,sizeof(Graph));
    printf("请输入图的节点数：");
    scanf("%d",&graph->node_size);
    graph->graphNodes = calloc(graph->node_size,sizeof(GraphNode));
    graph->table = calloc(graph->node_size,sizeof(int*));
    printf("请输入节点名称：");
    char* tmp = calloc(100,sizeof(char));
    for(int i=0;i<graph->node_size;i++){
        //创建节点并命名
        scanf("%s",tmp);
        graph->graphNodes[i].name = calloc(strlen(tmp) + 1,sizeof(char));
        strcpy(graph->graphNodes[i].name,tmp);
        //同时创建邻接矩阵的行
        graph->table[i] = calloc(graph->node_size,sizeof(int));
    }
    printf("请输入图的边数：");
    scanf("%d",&graph->edge_size);
    for(int i=0;i<graph->edge_size;i++){
        scanf("%s",tmp);
        int from = getNodePos(graph,tmp);
        scanf("%s",tmp);
        int to = getNodePos(graph,tmp);
        //两边相邻接
        graph->table[from][to] = 1;
    }
    free(tmp);
    return graph;
}

void printGraph(pGraph graph){
    printf("当前图共%d个节点，%d条边\n",graph->node_size,graph->edge_size);
    printf("节点为：\n");
    for(int i=0;i<graph->node_size;i++){
        printf("%s, ",graph->graphNodes[i].name);
    }
    printf("\n边为：\n");
    for(int from=0; from < graph->node_size; from++){
        for(int to=0;to<graph->node_size;to++){
            if(graph->table[from][to]>0){
                printf("%s -> %s\n",graph->graphNodes[from].name,graph->graphNodes[to].name);
            }
        }
    }
}

void depthFirstSearch(pGraph graph){
    printf("深度优先遍历的结果为：");
    int start_from = 0;
    pStack stack = make_stack();
    int* visit = calloc(graph->node_size,sizeof(int));
    pStackItem stackItem = calloc(1,sizeof(StackItem));
    stackItem->value = getNodePos(graph,graph->graphNodes[start_from].name);
    push(stack,stackItem);
    //栈非空
    while(peek(stack)){
        //当前要访问的节点序号
        stackItem = peek(stack);
        int from = stackItem->value;
        pop(stack);
        printf("%s -> ",graph->graphNodes[from].name);
        for( int to=0; to < graph->node_size; to++){
            if(!visit[to] && graph->table[from][to] > 0){
                visit[to] = 1;
                stackItem = calloc(1,sizeof(StackItem));
                stackItem->value = to;
                push(stack,stackItem);
            }
        }
        visit[from] = 1;
    }
    printf("\n");
    destroy_stack(stack);
    free(visit);
}

void broadFirstSearch(pGraph graph){
    printf("广度优先遍历的结果为：");
    int start_from = 0;
    pQueue queue = make_queue();
    int* visit = calloc(graph->node_size,sizeof(int));
    //将初始节点入队
    pQueueItem item = calloc(1, sizeof(QueueItem));
    item->value = start_from;
    enqueue(queue,item);
    //队列非空
    while (front(queue)){
        item = front(queue);
        int from = item->value;
        printf("%s -> ",graph->graphNodes[from].name);
        dequeue(queue);
        for(int to=0; to < graph->node_size; to++){
            //未访问目标节点且源和目的连通时
            if( !visit[to] && graph->table[from][to]>0){
                visit[to] = 1;
                item = calloc(1,sizeof(QueueItem));
                item->value = to;
                enqueue(queue,item);
            }
        }
        //源节点已访问
        visit[from] = 1;
    }
    printf("\n");
    destroy_queue(queue);
    free(visit);
}

void destroyGraph(pGraph graph){
    for(int i=0;i<graph->node_size;i++){
        free(graph->graphNodes[i].name);
    }
    free(graph->graphNodes);
    for(int i=0;i<graph->node_size;i++){
        free(graph->table[i]);
    }
    free(graph->table);
}